1. Field of the Invention
The present invention is related to a logic circuit for finding a "0" bit or a "1" bit by searching a binary bit string. Furthermore, the present invention is related to a carry-lookahead (CLA) circuit for use in arithmetic units handling a number of bits.
2. Prior Art
There are utilized logic circuits called a "0" bit searching circuit and a "1" bit searching circuit as logic circuits for constituting the hardware of a computer system. The logic circuits of this kind is used to find a "0" bit or a "1" bit by searching a binary bit string from the most significant bit to the least significant bit. The logic circuits are used to constitute a comparator for determining the largest number among a plurality of numbers, or a priority encoder used in a signal reception circuit having a plurality of input lines and provided, when receiving input signals at two or more input lines, for generating an output signal indicative of the input line receiving an input signal and having the highest priority among from the input lines receiving input signals.
On the other hand, a "1" bit searching circuit in accordance with the prior art is composed of a number of the logic gate connected in a matrix form or in a tree arrangement so that the circuit design tends to be complicated. Furthermore, there are a number of gates arranged from the input to the output so that it takes much time to pass input data therethrough.
On the other hand, carry lookahead circuits have been generally utilized in adder circuits for performing the addition operation of an N-bit input signal a&lt;N-1&gt;, a&lt;N-2&gt;, . . . , a&lt;0&gt;), referred to simply as a &lt;N-1:0&gt;, and an N-bit input signal b&lt;N-1&gt;, b&lt;N-2&gt;, . . . , b&lt;0&gt;, referred to simply as b&lt;N-1:0&gt;. An example of such a prior art CLA circuit is described in Japanese Patent Published Application No.Hei 3-150630. The prior art carry lookahead circuit as described is a so-called carry select adder which performs the addition operation both in the case that the carry-in signal is "0" and in the case that the carry-in signal is "1". In accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result.
There is described a carry lookahead circuit as illustrated in FIG. 2 in Japanese Patent Published Application No.Hei 3-150630. Propagate signals P&lt;3:0&gt; and generate signals G&lt;3:0&gt; are calculated during the addition operation of the input signals a&lt;3:0&gt; and the input signals b&lt;3:0&gt; by obtaining the EX-OR and the AND of each corresponding bits of the input signals a&lt;3:0&gt; and the input signals b&lt;3:0&gt;. The propagate signals P&lt;3:0&gt; and the generate signals G&lt;3:0&gt; are input to the carry lookahead circuit together with the carry-in signal Cin from the lower stage in order to generate carry signals C&lt;3:0&gt;.
FIG. 3 is a block diagram showing an exemplary carry select adder which performs the addition operation both in the case that the carry-in signal is "0" and in the case that the carry-in signal is "1" and, in accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result. The carry lookahead circuit CLA1 serves to performs the addition operation in the case that the carry-in signal is "1" while the carry lookahead circuit CLA2 serves to performs the addition operation in the case that the carry-in signal is "0". Either of the outputs of the carry lookahead circuits CLA1 and CLA2 are selected by means of a 2-1 multiplexer MUX.
A bit group 0 is arranged in the form of the 4-bit carry lookahead circuit as illustrated in FIG. 2 in order to handle &lt;0:3&gt; bits of data having a 32 bit length to be handled while seven bit groups 1 to 7 are arranged in the form of the 4-bit carry lookahead circuits each designed as illustrated in FIG. 3 in order to handle &lt;4:7&gt; bits, &lt;8:11&gt; bits, &lt;12:15&gt; bits, . . . &lt;28:31&gt; bits of the data. A carry lookahead circuit capable of handling 32 bits is then formed as illustrated in FIG. 1. C&lt;0&gt; to C&lt;3&gt;, C&lt;4&gt; to C&lt;7&gt;, C&lt;8&gt; to C&lt;11&gt;, . . . , C&lt;28&gt; to C&lt;31&gt; are sequentially generated in this order in the group 0, the group 1, . . . the group 7.
However, there is a following problem in the prior art CLA as described above. FIG. 4 shows the delay time required for completing the calculation, i.e., the delay time required for generating the carry signals C&lt;0&gt; to C&lt;31&gt;. Each of the carry lookahead circuits CLA1 and CLA2 of the respective carry lookahead circuits of the group 0 to the group 7 takes the same time T1 required for calculation. However, the multiplexer MUX of the carry lookahead circuit of the group 1 can initiate the operation required for selecting carry signals only after receiving the carry signal C&lt;3&gt; as given from the group 0. The delay time T2 of the multiplexer MUX is accumulated from the group 1 to the group 7 resulting in the total delay time T1+T2*7. Because of this, in accordance with the prior art technique, there is a problem that a longer delay time is required for completing the calculation of carry signals for data having a longer bit sequence.